package Epic;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

//http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
public class Coin_Change_Yue {

	public Coin_Change_Yue(){

	}
	/**
	 * MergeSort
	 * @param input
	 * @return
	 */
	public int[] Mergesort(int[] input){
		if(input.length ==1) return input;
		int flag = input.length/2;
		int[] leftarray = Arrays.copyOfRange(input,0,flag);
		int[] rightarray = Arrays.copyOfRange(input,flag,input.length);
		leftarray = Mergesort(leftarray);
		rightarray = Mergesort(rightarray);

		int[] ret = new int[input.length];
		int i=0,j=0,k=0;
		while(i<leftarray.length && j<rightarray.length){
			ret[k++] = leftarray[i]<rightarray[j] ? leftarray[i++] : rightarray[j++];
		}

		if(i<leftarray.length){
			while(k<input.length)
				ret[k++] = leftarray[i++];
		}
		if(j<rightarray.length){
			while(k<input.length)
				ret[k++] = rightarray[j++];
		}

		return ret;
	}
	
	/**
	 * Return the least number to change the money, each coin is infinite.
	 * @param coin
	 * @param money
	 * @return
	 */
	public int change(int[] coin, int money){
		int[] opt = new int[money+1];
		for(int i =1; i<money+1;++i)
			opt[i] = money;

		for(int num=1; num<money+1; ++num){
			for(int tempcoin: coin){
				if(num>=tempcoin && opt[num]>opt[num-tempcoin]+1){
					opt[num] = opt[num-tempcoin]+1;
				}
			}
		}

		return opt[money];
	}
	
	/**
	 * Return the number of ways to change a coin. One coin can only be used one time.
	 * We need a static variable "count"
	 * @param coin
	 * @param money
	 * @return
	 */
	private static int count;
	public int num_of_ways(int[] coin, int money){
		if(coin==null || coin.length==0) return 0;
		count=0;
		helper(coin,0,money);
		return count;
	}
	
	private void helper(int[] coin, int start, int cur_money){
		if(cur_money==0){
			count++;
		}
		for(int i=start;i<coin.length;++i){
			if(cur_money>=coin[i]){
				cur_money -= coin[i];
				helper(coin, i+1, cur_money);
			}
		}
	}
	
	/**
	 * Return the number of ways to change a coin. One coin can be used several times.
	 * @param coin
	 * @param money
	 * @return
	 */
	public int num_of_ways2(int[] coin, int money){
		if(coin==null || coin.length==0) return 0;
		int[] dp = new int[money+1];
		dp[0]=1;
		for(int i=0;i<coin.length;++i){
			for(int j=coin[i];j<=money;++j){
				dp[j] += dp[j-coin[i]];
			}
		}
		return dp[money];
	}
	
	/**
	 * DP solution of coin change, return a list like 7=<1,1,2,3>
	 * @param coin
	 * @param money
	 * @return
	 */
	public HashMap<Integer, ArrayList<Integer>> change2(int[] coin, int money){
		HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
		map.put(0, new ArrayList<Integer>());
		helper(coin, money,map);
		return map;
	}

	public int helper(int[] coin, int money,HashMap<Integer, ArrayList<Integer>> map){
		
		int count = Integer.MAX_VALUE;
		for(int i=coin.length-1;i>=0;i--){
			if(money-coin[i]<0) continue;
			int temp;
			if(map.containsKey(money-coin[i]))
				temp = map.get(money-coin[i]).size()+1;
			else 
				temp = helper(coin, money-coin[i], map)+1;
			if(temp<count){
				ArrayList<Integer> pre = new ArrayList<Integer>(map.get(money-coin[i]));
				pre.add(coin[i]);
				map.put(money, pre);
				count = temp;
			}
		}
		return count;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Coin_Change_Yue test = new Coin_Change_Yue();
		int[] test2 = {2,3};
		int[] testarray = test.Mergesort(test2);
		int testmoney = 6;
		System.out.print("The coins are: ");
		for (int i = 0; i < testarray.length; i++) {
			System.out.print(testarray[i]+" ");
		}
//		System.out.print("\nThe changes for money [" +testmoney+"] is: " );
//		System.out.println(test.change(testarray,testmoney));
		
		HashMap<Integer, ArrayList<Integer>> testmap = new HashMap<>();
		testmap = test.change2(test2, testmoney);
		System.out.print("\nThe changes for money [" +testmoney+"] is: " );
		for(int i : testmap.get(testmoney)){
			System.out.print(i+" ");
		}
		System.out.println("\nTotally number of coins is "+testmap.get(testmoney).size());
		System.out.println("\nTotal ways to change the coin is(one coin can only be used ONE time): [" + 
						test.num_of_ways(testarray, testmoney)+"]");
		System.out.println("Total ways to change the coin is(one coin can be used MANY times): [" + 
				test.num_of_ways2(testarray, testmoney)+"]");
		
	}

}
